package flashBack;

/**
 * @author zxc
 * @date 2023/01/16 09:30
 **/

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 题目 ：所有子集
 * 题目详述 ：
 * 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
 * 解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
 */
public class Subsets {
    /**
     * 思路 ：
     * 即，使用回溯法来获取数组nums中的所有子集
     * （1）若是数组nums中有n个元素的话，即需要有n步选择；
     * （即，判断当前正在遍历的数组元素是否需要被插入到result集合中）
     * 同时，需要注意到是，会去顺序遍历整个数组nums，无论其是否插入到result集合中，都不会在对此数组元素重新判断；
     * （2）每一步，都会有两个选择（1.插入到result集合中；2.不插入到result集合中）
     */
    public List<List<Integer>> subsets(int[] nums) {
        // 初始化结果集合，其所存储的是List集合（即，每一种解状态）
        List<List<Integer>> result = new LinkedList<>();
        if(nums.length == 0){
            return null;
        }
        /**
         * 参数分析 ：
         * （1）第一个参数 ：int[] nums
         * 所传入的是nums数组（题目要去求取的是，nums中所有子集合）;
         * （2）第二个参数 ：int index
         * 由于回溯法需要去进行n个步骤（n，为nums数组中的元素总数），即需要对于nums数组中的所有元素都去进行遍历;
         * ===》 index参数所指向的是当前遍历数组元素的下标;
         * （3）第三个参数 ：new LinkedList<Integer>()
         * ===》 此处的list集合，是用来存储一种解状态;
         * （4）第四个参数 ：List<List<Integer>> result
         * ===》 此处的result集合，是用来存储所有解状态的集合list;
         */
        result = flushBackNums(nums , 0 , new LinkedList<Integer>() , result);
        // 返回值 ：存储所有解状态的result集合；
        return result;
    }
    /**
     *  回溯算法核心 ：
     *  （1）判断是否经过n个步骤，已经获取到了一种解状态；
     *  （2）如何在每个步骤中，去进行选择（a.当前遍历的数组元素插入到subset中;b.当前遍历的数组元素不插入到subset中）
      */
    private List<List<Integer>> flushBackNums(int[] nums, int index, LinkedList<Integer> subset, List<List<Integer>> result) {
        // 即,当经历过n步后，即代表了已经生成了一种解状态。
        // 直接将该种解状态subset，加入到结果集合result中即可。
        if(index == nums.length){
            // 需要注意的是，result结果集合中所存储的是，subset解状态的拷贝；
            /**
             * 为什么只能够向result集合中添加subset解状态的拷贝，而不向result集合中添加subset解状态 ？
             * 原因 ：
             * （1）因为后续还需要通过修改subset，来获取其他所有解状态；
             * （2）若是后续对于subset进行修改的话，由于之前向result集合中所存储的是subset解状态，所以后续subset的修改也会去影响前面存储的解状态；
             * （3）若是将当前subset的拷贝存储到result集合中的话，则后续对于subset的修改则不会去影响前面所存储的所有解状态;
             */
            result.add(new LinkedList<>(subset));
        }
        // 即，类似于 树的深度优先遍历
        // 假设左子节点为 当前遍历的数组不插入subset；同时右子节点为 当前遍历的数组元素插入到subset
        else {
            // 当前遍历的数组元素不插入到subset中,由于未将元素插入到subset中，所以不需要去进行回溯
            // ===》 直接开启下一个步骤的选择即可
            flushBackNums(nums , index + 1, subset , result);
            // 类似于深度优先遍历，遍历到 树的最左子节点；
            // 回溯到其父节点后，在遍历父节点的右子节点；

            // 当前遍历的数组元素插入到subset中
            subset.add(nums[index]);
            flushBackNums(nums , index + 1 , subset , result);
            // 即，由于将元素插入到了subset中，所以需要进行回溯;(即，将subset中所存储的解状态尾元素删除即可)
            subset.removeLast();
        }
        return result;
    }
    /**
     * 分析 ：
     * 时间复杂度 ：O（2的n次方）; (由于每个nums数组中有n个元素 && 同时，每个元素都存在2个步骤  ===》 总共的选择总数 ：2的n次方)
     */
}
